home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / mint / utils / agrepsrc.zoo / sgrep.c < prev    next >
C/C++ Source or Header  |  1993-01-19  |  19KB  |  686 lines
  1. /* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  2. #include <stdio.h>
  3. #define MAXSYM  256
  4. #define MAXMEMBER 8192
  5. #define    CHARTYPE    unsigned char
  6. #define MaxError 20
  7. #define MAXPATT 256
  8. #define MAXLINE 1024
  9. #define MaxCan  2048
  10. #define BLOCKSIZE    8192
  11. #define MAX_SHIFT_2  4096
  12. #define ON      1
  13. #define LOG_ASCII 8
  14. #define LOG_DNA  3
  15. #define MAXMEMBER_1 65536
  16. #define LONG_EXAC  20
  17. #define LONG_APPX  24
  18. #define W_DELIM    2
  19.  
  20. extern COUNT, FNAME, SILENT, FILENAMEONLY, num_of_matched;
  21. extern DNA ;  /* DNA flag is set in checksg when pattern is DNA pattern and
  22.          p_size > 16  */
  23. extern WORDBOUND, WHOLELINE, NOUPPER;
  24. extern unsigned char CurrentFileName[],  Progname[]; 
  25. extern unsigned Mask[];
  26. extern unsigned endposition;
  27.  
  28. unsigned char BSize;                /* log_c m   */
  29. unsigned char char_map[MAXSYM];
  30.     
  31.  
  32. /* data area */
  33. int shift_1;
  34. CHARTYPE SHIFT[MAXSYM];
  35. CHARTYPE MEMBER[MAXMEMBER];
  36. CHARTYPE pat[MAXPATT];
  37. unsigned Hashmask;
  38. char MEMBER_1[MAXMEMBER_1];
  39. CHARTYPE TR[MAXSYM];
  40.  
  41. char_tr(pat, m)
  42.     unsigned char *pat;
  43.     int *m;
  44. {
  45. int i;
  46. unsigned char temp[MAXPATT];
  47.     for(i=0; i<MAXSYM; i++) TR[i] = i;
  48.     if(NOUPPER) {
  49.         for(i='A'; i<= 'Z'; i++) TR[i] = i + 'a' - 'A';
  50.     }
  51.     if(WORDBOUND) { /* SUN: To be added to be more complete */
  52.         TR['\n'] = TR['\t'] = TR[' '] = TR[','] = TR[';'] = TR[':'] = 
  53.             TR['!'] = TR['"'] = TR['?'] = TR['<'] = TR['>'] = 
  54.         TR['='] = TR['['] = TR[']'] = TR['\''] =
  55.             TR['('] = TR[')'] = TR['$'] = TR['/'] = TR['\\'] = W_DELIM;
  56.     }
  57.     if(WHOLELINE) {
  58.         memcpy(temp, pat, *m);
  59.         pat[0] = '\n';
  60.         memcpy(pat+1, temp, *m);
  61.         pat[*m+1] = '\n';
  62.         pat[*m+2] = 0;
  63.         *m = *m + 2;
  64.     }
  65. }
  66.  
  67. sgrep(pat, m, fd, D)
  68. CHARTYPE *pat;  int fd, m, D;
  69. { 
  70.     CHARTYPE text[BLOCKSIZE+2*MAXLINE+MAXPATT]; /* input text stream */
  71.     int offset = 2*MAXLINE;
  72.     int buf_end, num_read, i, start, end, residue = 0;
  73.     if(pat[0] == '^' || pat[0] == '$') pat[0] = '\n';
  74.     if(pat[m-1] == '^' || pat[m-1] == '$') pat[m-1] = '\n';
  75.     char_tr(pat, &m);   /* will change pat, and m if WHOLELINE is ON */
  76.     text[offset-1] = '\n';  /* initial case */
  77.     for(i=0; i < MAXLINE; i++) text[i] = 0;   /* security zone */
  78.     start = offset;   
  79.     if(WHOLELINE) start--;
  80.     if(m >= MAXPATT) {
  81.          fprintf(stderr, "%s: pattern too long\n", Progname);
  82.          exit(2);
  83.     }
  84.     if(D == 0) {
  85.     if(m > LONG_EXAC) m_preprocess(pat);
  86.     else prep_bm(pat, m);
  87.     }
  88.     else if (DNA) prep4(pat, m);
  89.      else     if(m >= LONG_APPX) am_preprocess(pat);
  90.         else {
  91.             prep(pat, m, D);
  92.             initmask(pat, Mask, m, 0, &endposition); 
  93.         }
  94.     for(i=1; i<=m; i++) text[BLOCKSIZE+offset+i] = pat[m-1];
  95.         /* to make sure the skip loop in bm() won't go out of bound */
  96.     while( (num_read = read(fd, text+offset, BLOCKSIZE)) > 0) 
  97.     {
  98.        buf_end = end = offset + num_read -1 ;
  99.        if(num_read < BLOCKSIZE) if(text[end] != '\n') text[++end] = '\n';
  100.        while(text[end]  != '\n' && end > offset) end--;
  101.        residue = buf_end - end + 1 ;
  102.        text[start-1] = '\n';
  103.        if(D==0)  {
  104.         if(m > LONG_EXAC) monkey(pat, m, text+start, text+end);
  105.         else bm(pat, m, text+start, text+end);
  106.        }
  107.        else {
  108.         if(DNA) monkey4( pat, m, text+start, text+end, D  );
  109.         else {
  110.           if(m >= LONG_APPX) a_monkey(pat, m, text+start, text+end, D);
  111.           else       agrep(pat, m, text+start, text+end, D);
  112.         }
  113.        }
  114.        if(FILENAMEONLY && num_of_matched) {
  115.             printf("%s\n", CurrentFileName);
  116.             return; }
  117.        start = offset - residue ;
  118.        if(start < MAXLINE) {
  119.             start = MAXLINE; 
  120.        }
  121.        strncpy(text+start, text+end, residue);
  122.        start++;
  123.     } /* end of while(num_read = ... */
  124.     return;
  125. } /* end sgrep */
  126.  
  127. /* SUN: bm assumes that the content of text[n]...text[n+m-1] is 
  128. pat[m-1] such that the skip loop is guaranteed to terminated */
  129.  
  130. bm(pat, m, text, textend)
  131.     CHARTYPE *text, *textend, *pat;  int m;
  132. {
  133. register int shift;
  134. register int  m1, j, d1; 
  135.  
  136. /*
  137. printf("%d\t", textend - text);
  138. printf("%c, %c", *text, *textend);
  139. */
  140.  
  141. d1 = shift_1;    /* at least 1 */
  142. m1 = m - 1;
  143. shift = 0;       
  144. while (text <= textend) {
  145.     shift = SHIFT[*(text += shift)];
  146.     while(shift) {          
  147.         shift = SHIFT[*(text += shift)];
  148.         shift = SHIFT[*(text += shift)];
  149.         shift = SHIFT[*(text += shift)];
  150.     }
  151.         j = 0;
  152.         while(TR[pat[m1 - j]] == TR[*(text - j)]) {
  153.             if(++j == m)  break;       /* if statement can be
  154.                             saved, but for safty ... */
  155.         }
  156.             if (j == m ) { 
  157.             if(text > textend) return;
  158.             if(WORDBOUND) {
  159.                 if(TR[*(text+1)] != W_DELIM) goto CONT;
  160.                 if(TR[*(text-m)] != W_DELIM) goto CONT;
  161.             }
  162.             num_of_matched++;
  163.             if(FILENAMEONLY) return;
  164.             if(!(COUNT)) {
  165.                 if(FNAME) printf("%s: ", CurrentFileName);
  166.                 while(*(--text) != '\n');
  167.                 while(*(++text) != '\n') putchar(*(text));
  168.                 putchar(*text);
  169.             }
  170.             else { while(*text != '\n') text++; } 
  171. CONT:
  172.             shift = 1;
  173.                 }
  174.         else shift = d1;
  175.   }
  176. return;
  177. }
  178.  
  179.   
  180. /* initmask() initializes the mask table for the pattern                    */ 
  181. /* endposition is a mask for the endposition of the pattern                 */
  182. /* endposition will contain k mask bits if the pattern contains k fragments */
  183. initmask(pattern, Mask, m, D, endposition)
  184. CHARTYPE *pattern; unsigned *Mask; register int m, D; unsigned *endposition;
  185. {
  186.   register unsigned Bit1, c;
  187.   register int i, j, frag_num;
  188.  
  189.   Bit1 = 1 << 31;    /* the first bit of Bit1 is 1, others 0.  */
  190.   frag_num = D+1; *endposition = 0;
  191.   for (i = 0; i < frag_num; i++) *endposition = *endposition | (Bit1 >> i);
  192.   *endposition = *endposition >> (m - frag_num);
  193.   for(i = 0; i < m; i++) 
  194.           if (pattern[i] == '^' || pattern[i] == '$') {
  195.               pattern[i] = '\n'; 
  196.           }
  197.   for(i = 0; i < MAXSYM; i++) Mask[i] = ~0;
  198.   for(i = 0; i < m; i++)     /* initialize the mask table */
  199.   {  c = pattern[i];
  200.      for ( j = 0; j < m; j++)
  201.            if( c == pattern[j] )
  202.                Mask[c] = Mask[c] & ~( Bit1 >> j ) ;
  203.   }
  204. }
  205.  
  206. prep(Pattern, M, D)             /* preprocessing for partitioning_bm */
  207.     CHARTYPE *Pattern;  /* can be fine-tuned to choose a better partition */
  208.     register int M, D;
  209. {
  210. register int i, j, k, p, shift;
  211. register unsigned m;
  212. unsigned hash, b_size = 3;
  213.     m = M/(D+1);
  214.     p = M - m*(D+1);
  215.     for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  216.     for (i = M-1; i>=p ; i--) {
  217.         shift = (M-1-i)%m;
  218.         hash = Pattern[i];
  219.         if(SHIFT[hash] > shift) SHIFT[hash] = shift;
  220.     }
  221. #ifdef DEBUG
  222.     for(i=0; i<M; i++) printf(" %d,", SHIFT[Pattern[i]]);
  223.     printf("\n");
  224. #endif
  225.     shift_1 = m;
  226.     for(i=0; i<D+1; i++) {
  227.         j = M-1 - m*i;
  228.         for(k=1; k<m; k++) {
  229.             for(p=0; p<D+1; p++) 
  230.                 if(Pattern[j-k] == Pattern[M-1-m*p]) 
  231.                     if(k < shift_1) shift_1 = k;
  232.         }
  233.     }
  234. #ifdef DEBUG
  235.     printf("\nshift_1 = %d", shift_1);
  236. #endif
  237.     if(shift_1 == 0) shift_1 = 1;
  238.     for(i=0; i<MAXMEMBER; i++) MEMBER[i] = 0;
  239.     if (m < 3) b_size = m;
  240.     for(i=0; i<D+1; i++) {
  241.         j = M-1 - m*i;
  242.         hash = 0;
  243.         for(k=0; k<b_size; k++) {
  244.             hash = (hash << 2) + Pattern[j-k];
  245.         }
  246. #ifdef DEBUG
  247.     printf(" hash = %d,", hash);
  248. #endif
  249.         MEMBER[hash] = 1;
  250.     }
  251. }
  252.  
  253.  
  254. agrep( pat, M, text, textend, D ) 
  255. int M, D ; register CHARTYPE *text, *textend, *pat;
  256. {
  257.   register int i;
  258.   register int m = M/(D+1);
  259.   register CHARTYPE *textstart;
  260.   register int shift, HASH;
  261.   int  j=0, k, m1, d1;
  262.   int  n, cdx;
  263.   int  Candidate[MaxCan][2], round, lastend=0;
  264.   unsigned R1[MaxError+1], R2[MaxError+1]; 
  265.   register unsigned int r1, endpos, c; 
  266.   unsigned currentpos;
  267.   unsigned Bit1;
  268.   unsigned r_newline;
  269.  
  270.   Candidate[0][0] = Candidate[0][1] = 0; 
  271.   d1 = shift_1;
  272.   cdx = 0;
  273.   if(m < 3) r1 = m;
  274.   else r1 = 3;
  275.   textstart = text;
  276.   shift = m-1;
  277.   while (text < textend) {
  278.     shift = SHIFT[*(text += shift)];
  279.     while(shift) {
  280.         shift = SHIFT[*(text += shift)];
  281.         shift = SHIFT[*(text += shift)];
  282.     }
  283.         j = 1; HASH = *text;
  284.         while(j < r1) { HASH = (HASH << 2) + *(text-j);
  285.                 j++; }
  286.             if (MEMBER[HASH]) { 
  287.             i = text - textstart;
  288.                          if((i - M - D - 10) > Candidate